package sum

import (
	"sort"
)

/*
找出三个数，要求三个数相加为0
我们可以想到，三个指针，分别指向三个数，按照一定顺序遍历。
1：首先我们先进行切片的排序
2：三个指针分别为start , end , index ，以index为中心，两侧start和end向index方向移动。
3：如果遇到重复的数字（之前出现的数字），将start = index - 1，
4：遍历切片，index从1开始，到末尾结束
5：子循环，将start和end指针向index方向移动。
6：如果nums[start] == nums[start - 1]，将satrt后移，因为之前计算过，不能计算第二次。
7：如果nums[end] == nums[end + 1]，则end前移，因为end是从后向前走的，并且不能计算第二次。
8：计算三个指针的总和。
9：如果从何等于0，将指针所指向的数存储，前指针后移，后指针前移，如果总和大于0，后指针前移，如果总和小于0，前指针后移。
*/

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	start, end, index, result, addnum, length := 0, 0, 0, make([][]int, 0), 0, len(nums)
	for index = 1; index < length-1; index++ {
		start, end = 0, length-1
		if index > 1 && nums[index] == nums[index-1] {
			start = index - 1
		}
		for start < index && end > index {
			if start > 0 && nums[start] == nums[start-1] {
				start++
				continue
			}
			if end < length-1 && nums[end] == nums[end+1] {
				end--
				continue
			}
			addnum = nums[start] + nums[index] + nums[end]
			if addnum == 0 {
				result = append(result, []int{nums[start], nums[index], nums[end]})
				start++
				end--
			} else if addnum < 0 {
				start++
			} else {
				end--
			}
		}
	}
	return result
}
